package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

/**
 * @ClassName QuikSort
 * @Description QuikSort
 * @Author wanghaiwei
 * @Date 2023/3/8 16:14
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] input = new int[]{21, 2, 4, 19, 33, 1, 7, 9, 2, 4};
        ArrayUtils.shuffle(input);
        System.out.println("quickSort排序前：" + Arrays.toString(input));
        quickSort(input, 0, input.length - 1);
        System.out.println("quickSort排序后：" + Arrays.toString(input));
    }

    /**
     * 参考文章：https://blog.csdn.net/qq_39181839/article/details/109478094
     *
     * @param input
     * @param begin
     * @param end
     */
    public static void quickSort(int[] input, int begin, int end) {
        int leftIdx = begin;
        int rightIdx = end;
        if (leftIdx >= rightIdx) {
            //此时说明已经只剩一个元素了，不需要排序
            return;
        }
        int pivotValue = input[leftIdx];
        while (leftIdx < rightIdx) {
            while (leftIdx < rightIdx && input[rightIdx] >= pivotValue) {
                rightIdx--;
            }
            input[leftIdx] = input[rightIdx];
            while (leftIdx < rightIdx && input[leftIdx] < pivotValue) {
                leftIdx++;
            }
            input[rightIdx] = input[leftIdx];
        }
        //将基准值放在"合适"的地方
        input[leftIdx] = pivotValue;
        quickSort(input, begin, leftIdx);
        quickSort(input, leftIdx + 1, end);
    }
}
